# -*- coding:utf-8 -*-
__author__ = 'gin.chen'

## 二维数组查找
"""
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，
判断数组中是否含有该整数
"""

##替换空格
"""
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.
则经过替换之后的字符串为We%20Are%20Happy。

"""


class Solution:

    def replaceSpace(self, s):
        if s == None or s == "": return ""
        if len(s) == 0: return ""
        return s.replace(' ', '%20')

    # array 二维列表
    def Find(self, target, array):
        # write code here
        # x = len(array[0])
        # y = len(array)
        # if x == 0 or y == 0:
        #     return 0
        # if array[0][x-1] < array[y-1][0]:
        #     array = list(zip(*array))
        # for i in range(0, len(array[0])):
        #     if array[0][i] <= target:
        #         for j in range(0, len(array)):
        #             if array[j][i] == target:
        #                 return 1
        # return 0
        x = len(array[0])
        y = len(array) - 1
        i = 0
        j = y
        while i < x and j >= 0:
            if target == array[j][i]:
                return 1
            if target > array[j][i]:
                i += 1
            else:
                j -= 1
        return 0


if __name__ == '__main__':
    x = [[2, 4, 8],
         [5, 7, 9],
         [8, 10, 14],
         [12, 13, 15]]
    # x = [[]]
    print(Solution().Find(10, x))
    print(Solution().replaceSpace("''"))
